/*
 * To change this template, choose Tools | Templates and open the template in
 * the editor.
 */
package AA;

/**
 *
 * @author asc
 */

public class P101
{
    public char[] cadenaA;
    public char[] cadenaB;
    int [][]distance;
    public String bestSolution(String[] args){
        String Sol="";
        cadenaA=args[0].toCharArray();
        cadenaB=args[1].toCharArray();
        distance = new int[cadenaA.length+1][cadenaB.length+1];
        computeLevenshteinDistance(cadenaA, cadenaB);
        /*
        for (int i = 0; i <= cadenaA.length; i++) {
            for (int j = 0; j <= cadenaB.length; j++) {
                System.out.print(distance[i][j] + "\t");
            }
            System.out.print("\n");
        }
        */
        int posX=cadenaA.length;
        int posY=cadenaB.length;
        
        while(posX > 0 || posY > 0){
            //Caso Base implicito    
            //System.out.print(String.valueOf(posX) + " " + String.valueOf(posY) + "\n");
            if(posX > 0 && posY >0)
            {
                int dif = (cadenaA[posX-1]!=cadenaB[posY-1]?1:0);
                if(distance[posX][posY] == distance[posX-1][posY-1]+dif){
                    Sol = "s"+cadenaA[posX-1]+""+cadenaB[posY-1]+ Sol;
                    posX--;
                    posY--;
                }
                else if(distance[posX][posY] == distance[posX-1][posY]+1){
                    Sol = "b"+cadenaA[posX-1]+ Sol;
                    posX--;
                }
                else if(distance[posX][posY] == distance[posX][posY-1]+1){
                    Sol = "i"+cadenaB[posY-1]+""+ Sol;
                    posY--;
                }
            }
            else if(posX > 0)
            {
                if(distance[posX][posY] == distance[posX-1][posY]+1){
                    Sol = "b"+cadenaA[posX-1]+ Sol;
                    posX--;
                }
            }
            else if(posY > 0)
            {
                if(distance[posX][posY] == distance[posX][posY-1]+1){
                    Sol = "i"+cadenaB[posY-1]+""+ Sol;
                    posY--;
                }
            }
        }

        return Sol;
    }
    
     public static int minimum(int a, int b, int c) {
        if(a<=b && a<=c)
        {
            return a;
        } 
        if(b<=a && b<=c)
        {
            return b;
        }
        return c;
     }
 
    public int computeLevenshteinDistance(char [] str1, char [] str2) {
        for(int i=0;i<=str1.length;i++)
        {
                distance[i][0]=i;
        }
        for(int j=0;j<=str2.length;j++)
        {
                distance[0][j]=j;
        }
        for(int i=1;i<=str1.length;i++)
        {
            for(int j=1;j<=str2.length;j++)
            { 
                  distance[i][j]= minimum(distance[i-1][j]+1,
                                        distance[i][j-1]+1,
                                        distance[i-1][j-1]+
                                        ((str1[i-1]==str2[j-1])?0:1));
            }
        }
        return distance[str1.length][str2.length];
 
    }
    public static void main(String[] args)
    {
        P101 p = new P101();
        System.out.print(p.bestSolution(args));
    }
    
}
